package com.company.modeldesign;

import java.util.LinkedList;

public class MedianFinder {


    LinkedList<Float> cache = new LinkedList<>();

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {

    }




    private int binaryFindIndex(int num) {
        int left = 0;
        int right = cache.size();
        int mid = (left + right) / 2;


        while (left < mid && mid < right) {
            Float std = cache.get(mid);
            if (std > num) {//左半区
                right = mid;
            } else if (std < num) {//右边区
                left = mid;
            }else {
                return mid;
            }
            mid = (left+right)/2;
        }
        return mid;
    }

    public void addNum(int num) {
        int i = binaryFindIndex(num);
        cache.add(i, (float) num);
    }

    public double findMedian() {
        int size = cache.size();
        if (size % 2 == 0) {
            return (cache.get(size / 2) + cache.get((size / 2) - 1)) / 2;
        } else {
            return cache.get(size / 2);
        }
    }
}
